/*
 * @ Created with Clion
 * @ Author Morbid
 * @ Date 2022/07/25
 * @ Time 11:36
 */

/*!
 * 定义链栈(不带头节点)
 * 实现链栈基本操作
 */

#include <cstdlib>
typedef int ElemType;

typedef struct SNode {
    ElemType data;
    struct SNode *next;
} SNode, *ListStack;

/*!
 * 初始化链栈
 * @param S 栈
 */
void InitStack(ListStack &S) {
    S = nullptr;
}

/*!
 * 判断栈是否为空
 * @param S 栈
 * @return 栈空返回true,否则返回false
 */
bool StackEmpty(ListStack S) {
    if (S == nullptr)
        return true;
    else
        return false;
}

/*!
 * 入栈
 * @param S 链栈
 * @param x 入栈元素
 * @return 入栈成功返回true，否则返回false
 */
bool Push(ListStack &S, ElemType x) {
    auto *q = (SNode *) malloc(sizeof(SNode));
    if (q == nullptr)
        return false;
    q->data = x;
    q->next = S;
    S = q;
    return true;
};

/*!
 * 出栈
 * @param S 栈
 * @param x 存放出栈元素的变量
 * @return 出栈成功返回true,否则返回false
 */
bool Pop(ListStack &S, ElemType &x) {
    if (StackEmpty(S))
        return false;
    SNode *q = S;
    x = q->data;
    S = S->next;
    free(q);
    return true;
}

/*!
 * 获取栈顶元素
 * @param S 栈
 * @param x 存储栈顶元素的变量
 * @return 获取成功返回true，否则返回false
 */
bool GetTop(ListStack S, ElemType &x) {
    if (StackEmpty(S))
        return false;
    x = S->data;
    return true;
}